Dynamically estimating the position of a moving person or object, or “tracking,” has been the subject of intense study for decades. Tracking people and objects indoors from signal strength measurements has applications as diverse as security monitoring, self-guided museum tours and personalization of communications services. Accurate dynamic tracking in real-time has been elusive, though, because signal propagation in buildings and the paths that people follow are complex.
The widespread deployment of wireless networks in buildings provides an opportunity to estimate the position of people and objects in real-time for emergency response, protection of corporate assets, and personalized, position-based communications. Consequently, many approaches to static position and dynamic tracking from wireless signal strength measurements have been developed, at least in theory. Typically, tracking involves updating static position estimates using a motion model.
Relating received signal strength (RSS) to position is key to estimating the position of either a static or moving object. Several parametric propagation models that describe path loss across a region have been devised, but none has been unequivocally accepted (see, e.g., Molkdar, “Review on Radio Propagation Into and Within Buildings,” IEEE Proceedings-H, vol. 138, pp. 61-73, 1991; and Hashemi, “The Indoor Radio Propagation Channel,” Proceedings of the IEEE, vol. 81, pp. 943-968, 1993). Many require restrictive assumptions.
The most common models are based on inverse exponent laws: 10 log10L(d)=γ log10d+Lref, where d is distance, L(d) is actual path loss and Lref is path loss at a reference distance. Values for γ range from about 1.5 to 5 depending on channel conditions, such as whether the target position is line-of-sight down a corridor or whether the transmitter and receiver are on adjacent floors (see, e.g., Rappaport, et al., “UHF Fading in Factories,” IEEE Journal Selected Area of Communications, vol. 7, pp. 40-48, 1989; Rappaport, “Indoor Radio Communications for Factories of the Subsequent,” IEEE Communications Magazine, pp. 15-24, May 1989; Saleh, et al., “A Statistical Model for Indoor Multipath Propagation,” IEEE Journal Selected Area of Communications, vol. 5, pp. 128-137, 1987; Hashemi, supra; and references therein). There can also be additional log-normal shadowing loss with a standard deviation ranging from 3 decibels (dB) to 15 dB that affects RSS readings (id.). All these sources of variation need to be modeled for position estimation and tracking based on a propagation model to be effective.
More ambitious propagation models do not rely solely on distance but also include the loss incurred from walls, floors, partitions and other obstacles that may lie between the transmitter and the receiver. Path loss can then be determined by adding up attenuation estimates for the various obstacles (see, e.g., Seidel, et al., “900 MHz Path Loss and Prediction Techniques for In Building Communications System Designs,” Proceedings 41st Vehicular Technology Conference, St. Louis Mo., VTC 91, 1991). In practice, however, these extended path loss models offer little improvement over exponent models.
Including detailed information about the composition of the walls, floors and other structures in the building can help, but this information is difficult to obtain. Moreover, even sophisticated ray-tracing models that take detailed building maps and materials into account, such as the well-known WISE software tool (see, e.g., Fortune, et al., “WISE Design of Indoor Wireless Systems: Practical Computation and Optimization,” IEEE Computational Science and Engineering, vol. 2, pp. 58-68), have typical errors of 6 dB, which is far too high for accurate tracking. These tools may however be used in planning out the position and number of access points (APs) as well as the distribution of training positions.
Nonetheless, some position estimation algorithms have been based on path loss models (see, e.g., Chen, et al., “Signal Strength Based Indoor Geoposition,” Proceedings IEEE Conference on Communications, New York, 2002). The parameters of the path loss model may be estimated from a set of training data with known positions using a regression model that includes wall attenuation and a path loss exponent. Position estimates are then based on the fitted model.
Several approaches to indoor tracking have avoided path loss models and instead drawn an empirical mean RSS map for each of a set of NAP APs by interpolating the mean RSSs obtained at a set of known training positions. RSS measurements at an unknown position are then compared to the RSS maps to estimate the receiver's position. Because there is no path loss model, the positions of the APs need not be known, and indeed are not used in any way.
Some systems require training measurements to be constantly generated by transceivers, called “emitters,” at fixed positions (see, e.g., Krishnan, et al. “A System for LEASE: System Position Estimation Assisted by Stationary Emitters for Indoor RF Wireless Networks,” In Proceedings of IEEE Infocom, 2004). The emitters allow the current propagation environment, which depends on factors that change over time, such as building occupancy, to be re-estimated routinely. A signal strength mean map is estimated by fitting a nonparametric smooth function to the training data using the coordinates of their positions as the covariates in the fitted model. To estimate a position, the J strongest RSS readings may be compared to the corresponding J smoothed RSS maps, ignoring the NAP−J weaker signals. The position of the nearest neighbor using Euclidean distance is declared to be the estimated position.
Perhaps the most well-known algorithm for tracking is the Kalman filter, which has been used for indoor tracking in, e.g., Guvenc, et al., “Enhancements to RSS Based Indoor Tracking Systems Using Kalman Filters,” International Signal Processing Conference and Global Signal Processing Expo, Dallas, Tex., 2003, and Fox, et al., “Bayesian Techniques for Position Estimation,” IEEE Pervasive Computing, vol. 2, no. 3, 2003, for example. Kalman filters are based on linear motion. Unfortunately, people often do not take linear paths indoors because doors, walls and corners frequently interfere with them. Particle filters have sometimes been used, but their computations are burdensome and not suited to online tracking.
Voronoi filters that restrict movement to a graph that by design prohibits wall crossing have also been used (see, e.g., Liao, et al., “Voronoi Tracking: Position Estimation Using Sparse and Noisy Sensor Data,” Proceedings of the International Conference on Intelligent Robots and Systems,” IEEE/RSJ, 2003). This procedure can be more accurate, but it also requires significantly more computation.
Round-trip delay (see, e.g., Low, et al., “Pulse Detection Algorithm for Line-of-Sight (LOS) UWB Ranging Applications,” IEEE Antennas and Propagation Letters, vol. 4, pp. 63-67, 2004) has been used to estimate position and is potentially far more accurate than techniques based on signal strength, but it requires high bandwidth (ultra wideband) signals and specialized hardware. For example, ranging involves detecting the return pulse reflected from a passive device on the target and measuring the round trip delay. For line-of-sight positions, this method can achieve centimeter accuracy over distances of about 20 m (id.).
All of the aforementioned approaches suffer from extensive training, undue computational complexity, inadequate positional accuracy or a combination of these. What is needed in the art is a simple, system and method for performing dynamic tracking that performs well with limited training data. More specifically, what is needed in the art is a system and method that is not required to depend upon either a propagation model or a motion model of the region in which the tracking takes place.